package chap03.InsertSort;

/**
 * Created by root on 2017/7/12.
 */
public class ArrayIns
{
    private long[] a;                 // ref to array a
    private int nElems;               // number of data items
    //--------------------------------------------------------------
    public ArrayIns(int max)          // constructor
    {
        a = new long[max];                 // create the array
        nElems = 0;                        // no items yet
    }
    //--------------------------------------------------------------
    public void insert(long value)    // put element into array
    {
        a[nElems] = value;             // insert it
        nElems++;                      // increment size
    }
    //--------------------------------------------------------------
    public void display()             // displays array contents
    {
        for(int j=0; j<nElems; j++)       // for each element,
            System.out.print(a[j] + " ");  // display it
        System.out.println("");
    }
    //--------------------------------------------------------------

    /**
     * 插入排序用for和while都能循环，while更适合在某种情况下终止循环，
     * for适合在某个范围内循环，所以while更适合插入循序
     */

    public void InsertSort() {
        int out,in;
        long temp;
        for (out=1; out<nElems; out++) {
            temp = a[out];
            for (in=out; in>0; in--) {
                if (a[in-1] > temp) {
                    a[in] = a[in-1];
                } else {
                    break;
                }
            }
            a[in] = temp;
        }
    }
    public void InsertSortWhile() {
        int out,in;
        long temp;
        for (out=1; out<nElems; out++) {
            temp = a[out];
            in = out;
            while (in>0 && a[in-1] > temp) {
                a[in] = a[in-1];
                in--;
            }
            a[in] = temp;
        }
    }

    public void InsertSortWhileNoDups() {
        int out,in;
        long temp;
        int count = 0;
        final long FLAG = -1;
        for (out=1; out<nElems; out++) {
            temp = a[out];
            in = out;
            while (in>0 && a[in - 1] >= temp && a[in - 1] != -1) {
                if (a[in-1] == temp) {
                    temp = -1;
                    count++;
                }
                a[in] = a[in-1];
                in--;
            }
            a[in] = temp;
        }
        nElems = nElems -count;
        for (int i=0;i<nElems;i++) {
            a[i] = a[i+count];
        }
    }

    public void InsertSortWhileNums() {
        int out,in;
        long temp;
        int compareNum = 0;
        int copyNum = 0;
        for (out=1; out<nElems; out++) {
            temp = a[out];
            in = out;
            while (in>0) {
                if (a[in-1] > temp) {
                    a[in] = a[in-1];
                    in--;
                    compareNum++;
                    copyNum++;
                } else {
                    compareNum++;
                    break;
                }
            }
            a[in] = temp;
        }
        System.out.println("selectSort compareNum is " + compareNum + " 次");
        System.out.println("selectSort copyNum is " + copyNum + " 次");
    }
    //--------------------------------------------------------------
    private void swap(int one, int two)
    {
        long temp = a[one];
        a[one] = a[two];
        a[two] = temp;
    }
//--------------------------------------------------------------
}  // end class ArrayBub
